// 基于快速排序

var getLeastNumbers = function (arr, k) {
  let len = arr.length;
  if (!len || !k) return [];
  let start = 0;
  let end = len - 1;
  // 寻找一次标杆元素的位置
  let index = quickSort(arr, start, end);
  while (index !== k) {
    if (index > k) {
      end = index - 1;
      index = quickSort(arr, start, end);
    } else if (index < k) {
      start = index + 1;
      index = quickSort(arr, start, end);
    }
  }
  return arr.slice(0, k);
};

function quickSort(arr, left, right) {
  let pivot = arr[left];
  while (left < right) {
    while (left < right && arr[right] >= pivot) right--;
    arr[left] = arr[right];
    while (left < right && arr[left] < pivot) left++;
    arr[right] = arr[left];
  }
  arr[left] = pivot;
  return left;
}
